МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 4 Структура даних Черга  1 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги.Набуття практичних навичок побудовичерги, дослідженнядинаміки її вмісту та використання черг для розв'язання прикладних задач. 2 Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full)або деком (push_left, push_right, pop_left, pop_right, front_left, front_right,empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queueunderflow) і "переповнення черги" (queueoverflow) або "втрати значимості деку"(dequnderflow) і "переповнення деку" (deqoverflow). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. Змоделювати дек, в якому до опису деку додано дві функціїcommute_leftта commute_right, якізаміняють елемент, що знаходиться в кінці деку (правому або лівому відповідно), на заданий елемент. Кожний раз, коли після операції додаванняв лівому або в правому кінці деку опиниться число більше за 50, то треба зменшити його значення на 10. Після обробки всієї заданої вхідної послідовності перевірити, чи буде дек “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.). ). 3 Алгоритм роз’вязку задачі: Дек організовуємо у вигляді класу. Це дає можливість працювати з усіма типами даних. Спочатку по черзі вносимо елементи. Дані вносяться в дек з права якщо елемент додатній та парний і вносяться з ліва якщо елемент не парний, а якщо елемент від’ємний парний то він робить оперекію pop з права, не парний то з ліва. 4.Динаміка вмісту деку: Внесення в основний дек вхідних даних(п– правий край, л – лівий край) 1)push_left(5) 5           2)push_left(9) 9 5          3)push_right(14) 9 5 14         4)push_right(54); 9 5 14 54        5)push_left(63) 63 9 5 14 54       6)push_right (4) 63 9 5 14 54 4      7)pop_left(-3) 9 5 14 54 4       8)push_left(5) 5 9 5 14 54 4      9)pop_right (-6) 5 9 5 14 54       10)push_left(5) 5 5 9 5 14 54       Перевірка на дзеркальність: 5≠44 5≠14 9≠5 Отже дек не дзеркальний. If (top-left()==top.right()) Pop_left(); pop_right(); 5 Результати виконання програми: / Висновки: На цій лабораторній роботі я ознайомилась зcтруктурою даних черга. А саме із різновидом черги – дек. Дослідила принципи і методи роботи з чергою та деком. Додатки: #include<stdio.h> #include<iostream> #include<conio.h> usingnamespace std; class deq{ private: int left,right; int count; int *items; int Capacity; public: deq(int n){ Capacity = n; items = newint[Capacity]; count = 0; left = Capacity / 2; right = left - 1; } ~deq(){delete[] items;} void push_right(int it){ if (count < Capacity){ if(right == Capacity - 1 ){ for (int i = left - 1; i < right; i++) items[i]=items[i + 1]; items[right] = it; left--; } else items[++right] = it; count++; } } void push_left(int it){ if (count < Capacity){ if(left == 0){ for (int i = right + 1; i > 0; i--) items[i] = items[i - 1]; items[left] = it; right++; } else items[--left] = it; count++; } } int size(){return count;} bool emp...